home *** CD-ROM | disk | FTP | other *** search
/ CD Ware Multimedia 1995 May / cd Ware (Juegos) Epimundo.iso / DOS / C / HZIP.ZIP / HUFFENC.CPP < prev    next >
Encoding:
C/C++ Source or Header  |  1991-01-08  |  3.8 KB  |  160 lines
  1. ////////////////////////////////////////////////////
  2. // Huffman encoder implementation file huffenc.cpp
  3. // Copyright (c) 1991 Azarona Software
  4. // All rights reserved. 
  5. ////////////////////////////////////////////////////
  6.  
  7. #include "huffenc.h"
  8.  
  9. huff_encoder::huff_encoder(int ns, int mcl)
  10. {
  11.   int k;
  12.   num_symbols = ns; 
  13.   max_code_len = mcl;
  14.   codes = new unsigned[ns];
  15.   code_lengths = new char[ns];
  16.   for (k = 0; k<ns; k++) code_lengths[k] = 0;
  17.   leaf_depths = new char[ns];
  18.   counts = new long[ns];
  19.   for (k = 0; k<ns; k++) counts[k] = 0;
  20.   sorted_counts = new long[ns];
  21.   smap = new unsigned char[ns];
  22.   for (k = 0; k<ns; k++) smap[k] = k;
  23.   reset_encoding();
  24. }
  25.  
  26. huff_encoder::~huff_encoder(void)
  27. {
  28.   delete[num_symbols] codes;
  29.   delete[num_symbols] code_lengths;
  30.   delete[num_symbols] leaf_depths;
  31.   delete[num_symbols] counts;
  32.   delete[num_symbols] smap;
  33. }
  34.  
  35. int huff_encoder::generate_codes(void)
  36. // First sort weights in decreasing order, call package
  37. // merge to find the leaf depth (code length) of each 
  38. // symbol, then, remap these depths so that they are
  39. // sorted in increasing order of depth, then,
  40. // generate the huffman codes from the sorted depth array.
  41. // Returns 1 if successful, 0 if not
  42. {
  43.   int rv;
  44.  
  45.   for (rv = 0; rv<num_symbols; rv++) sorted_counts[rv] = counts[rv];
  46.   qs(sorted_counts, smap, num_symbols);
  47.   rv = package_merge(sorted_counts, smap, num_symbols, 
  48.                      max_code_len, code_lengths);
  49.   if (rv) {
  50.      for (int k = 0; k<num_symbols; k++) 
  51.          leaf_depths[k] = code_lengths[smap[k]];
  52.      make_codes(leaf_depths, codes, smap, num_symbols, max_code_len);
  53.   }
  54.   return rv;
  55. }
  56.  
  57. void huff_encoder::reset_encoding(void)
  58. {
  59.   currbyte = 0; currbit = 0;
  60. }
  61.  
  62. void huff_encoder::flushbits(void)
  63. {
  64.   if (currbit) {
  65.      fputc(currbyte, fout);
  66.      currbyte = 0; currbit = 0;
  67.   }
  68. }
  69.  
  70. union twobytes {
  71.   unsigned code;
  72.   struct {
  73.     unsigned char ch1, ch2;
  74.   } arr;
  75. };
  76.  
  77. unsigned char mask[9] = { 
  78.   0xff, 0xfe, 0xfc, 0xf8, 0xf0, 0xe0, 0xc0, 0x80, 0x00
  79. };
  80.  
  81. void huff_encoder::encode_symbol(int sym)
  82. {
  83.   twobytes tb;
  84.   tb.code = codes[sym]; 
  85.   unsigned char nbits = code_lengths[sym];
  86.  
  87.   while(nbits) {
  88.     unsigned char codebyte = (tb.arr.ch2 >> currbit);
  89.     char blib = 8 - currbit;
  90.     if (blib > nbits) { // Will have partial currbyte when through
  91.        currbyte |= (codebyte & mask[blib-nbits]);
  92.        currbit += nbits;
  93.        return;
  94.     }
  95.     else { // Byte will be full, so transfer out
  96.        currbyte |= codebyte;
  97.        tb.code <<= blib;
  98.        nbits -= blib;
  99.        fputc(currbyte, fout);
  100.        currbyte = 0; currbit = 0;
  101.     }
  102.   }
  103. }
  104.  
  105.  
  106. void huff_encoder::encode(FILE *fo, FILE *fi)
  107. {
  108.   fout = fo; fin = fi;
  109.   
  110.   reset_encoding();
  111.  
  112.   while(!feof(fin)) {
  113.     int c = fgetc(fin);
  114.     if (c != -1) encode_symbol(c);
  115.   }
  116.  
  117.   flushbits();
  118. }
  119.  
  120. void huff_encoder::dump_codes(FILE *f, long locn)
  121. {
  122.   fseek(f, locn, SEEK_SET);
  123.   fwrite(&num_symbols, sizeof(int), 1, f);
  124.   fwrite(codes, sizeof(unsigned), num_symbols, f);
  125.   fwrite(code_lengths, sizeof(char), num_symbols, f);
  126. }
  127.  
  128.  
  129. void huff_encoder::print_bits(char nbits, unsigned code)
  130. {
  131.   printf("%2d - ", nbits);
  132.   for (int i = 0; i<nbits; i++) {
  133.       if (code & 0x8000) putchar('1'); else putchar('0');
  134.       code <<= 1;
  135.   }
  136. }
  137.  
  138.  
  139. void huff_encoder::print_data(int show_sorted)
  140. {
  141.   int j;
  142.  
  143.   printf("\n\nsym: count lv   code\n\n");
  144.  
  145.   if (show_sorted) {
  146.      for (j = 0; j<num_symbols; j++) {
  147.          printf("%3d: %5lu ", smap[j], sorted_counts[j]);
  148.          print_bits(leaf_depths[j], codes[smap[j]]);
  149.          printf("\n");
  150.      }
  151.   }
  152.   else {
  153.     for (j = 0; j<num_symbols; j++) {
  154.         printf("%3d: %5lu ", j, counts[j]);
  155.         print_bits(code_lengths[j], codes[j]);
  156.         printf("\n");
  157.     }
  158.   }
  159. }
  160.